package chapter15.pp15_8;

import chapter15.pp4_2.LinnearNode;
import chapter4.pp4_2.LindedStack;
import chapter4.pp4_2.StackADT;
import chapter5.pp5_1.LInedQueue;
import chapter6.练习题.pp6_8.ArrayUnorderedList;
import chapter6.练习题.pp6_8.UnorderedListADT;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Network<T> implements NetworkADT {
    protected final int DEFAULT_CAPACITY = 5;
    protected int numVertices;    // number of vertices in the graph
    protected boolean[][] adjMatrix;    // adjacency matrix
    protected T[] vertices;    // values of vertices
    protected int modCount;
    protected double[][] Weight;
    LinnearNode[] temp;

    public Network() {
        numVertices = 0;
        this.adjMatrix = new boolean[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
        this.vertices = (T[]) (new Object[DEFAULT_CAPACITY]);
        this.Weight = new double[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
        this.temp = (LinnearNode[]) new LinnearNode[DEFAULT_CAPACITY];

    }
    @Override
    public String toString()
    {
        if (numVertices == 0)
            return "Graph is empty";

        String result = new String("");

        result += "Adjacency Matrix\n";
        result += "----------------\n";
        result += "index\t";

        for (int i = 0; i < numVertices; i++)
        {
            result += "" + i;
            if (i < 10)
                result += " ";
        }
        result += "\n\n";

        for (int i = 0; i < numVertices; i++)
        {
            result += "" + i + "\t";

            for (int j = 0; j < numVertices; j++)
            {
                if (adjMatrix[i][j])
                    result += "1 ";
                else
                    result += "0 ";
            }
            result += "\n";
        }

        result += "\n\nVertex Values";
        result += "\n-------------\n";
        result += "index\tvalue\n\n";

        for (int i = 0; i < numVertices; i++)
        {
            result += "" + i + "\t";
            result += vertices[i].toString() + "\n";
        }
        result += "\n";

        result += "Weight weight\n";
        result += "----------------\n";
        result += "index\t";

        for (int i = 0; i < numVertices; i++)
        {
            result += "" + i;
            if (i < 10)
                result += " ";
        }
        result += "\n\n";

        for (int i = 0; i < numVertices; i++)
        {
            result += "" + i + "\t";

            for (int j = 0; j < numVertices; j++)
            {
                if (adjMatrix[i][j])
                    result += Weight[i][j]+"  ";
                else
                    result += "0 "+"  ";
            }
            result += "\n";
        }
        return result;
    }
    public void addEdge(int index1, int index2)
    {
        if (indexIsValid(index1) && indexIsValid(index2))
        {
            adjMatrix[index1][index2] = true;
            adjMatrix[index2][index1] = true;
            modCount++;
        }
    }
    public void removeEdge(int index1, int index2)
    {
        // To be completed as a Programming Project
        if (indexIsValid(index1) && indexIsValid(index2))
        {
            adjMatrix[index1][index2] = false;
            adjMatrix[index2][index1] = false;
            modCount++;
        }
    }
    @Override
    public void addEdge(Object vertex1, Object vertex2, double weight) {

        addEdge(getIndex((T) vertex1), getIndex((T) vertex2));
        Weight[getIndex((T) vertex1)][getIndex((T) vertex2)]=weight;
        Weight[getIndex((T) vertex2)][getIndex((T) vertex1)]=weight;
//        for (int i =0;i<numVertices;i++){
//            for (int j=0;j<numVertices;j++){
//                if (adjMatrix[i][j]==false){
//                    Weight[i][j]=10000;
//                }
//            }
//        }
    }


    public void addVertex1(T v)
    {
        LinnearNode node = new LinnearNode();
        node.setElement(v);
        if (temp[0]==null){
            temp[0]=node;
        }
        vertices[numVertices]=v;
        temp[numVertices]=  node;
        numVertices++;
    }

//    public void addEdge12(T vertex1,T vertex2,double weight){
//            addEdge12(getIndex(vertex1),getIndex(vertex2));
//      //  Weight[getIndex((T) vertex1)][getIndex((T) vertex2)]=weight;
//
//    }

    public void addEdge12(int start,int end,double weight){
//        LinnearNode node = new LinnearNode();
//
//        node.setElement(vertices[end]);
//        temp[start].setNext(node);
        while (!(temp[start].getNext() ==null)){
            temp[start]=temp[start].getNext();
        }
        temp[start].setNext(temp[end]);
        temp[end].setWeight(weight);
    }


//    public void addEdge1(T vertex1, T vertex2){
//        int a =getIndex(vertex1);
//        int b =getIndex(vertex2);
//        while (!(temp[a].getNext() ==null)){
//            temp[a]=temp[a].getNext();
//        }
//        temp[a].setNext(temp[b]);
//    }
//

    @Override
    public double shortestPathWeight(Object vertex1, Object vertex2) {
        return shortestPathWeight(getIndex((T) vertex1),getIndex((T) vertex2));
    }

    
    public double shortestPathWeight(int start,int end){

//        Double[] temp = new Double[100];
//        Double result=0.0;
//        int a =0;
//        int b =0;
//        int c=0;
//        for (int i =0;i<end+1;i++){
//            start=c;
//            result=0.0;
//            for (int j =b;j<end;j++) {
//                result=0.0;
//                start=a;
//                for(int r=b;r<end;r++){
//                    result += Weight[start][r + 1];
//                    start=r+1;
//                    }
//                temp[a]=result;
//                a++;
//                b=b+2;
//            }
//
//
//            a++;
//            b++;
//        }
//
//            Double min = temp[0];
////            for (Double i : temp) {
////                if (i < min) {
////                    min = i;
////                }
////            }
//            for (int r =0;r<end;r++){
//                if (temp[r+1]<min&&temp[r+1]>0){
//                    min=temp[r+1];
//                }
//            }
//
//        return min;

        //Dijkstra算法

        double[] dis=new double[numVertices];//保存对应位置的距源点的最小权重

        boolean[] judge=new boolean[numVertices];//判断对应位置是否已经被查找

        int a =0;//记录位置
      int[] pre = new int[numVertices];

      for (int i =0;i<numVertices;i++){
          pre[i]=i;
          dis[i]=Weight[start][i];
          judge[i]=false;
      }

        judge[start]=true;

      for (int b=0;b<numVertices;b++){
          double min = 1000;//很大就OK
          for (int c =0;c<numVertices;c++){
              if (!judge[c]&&dis[c]<min){
                  min=dis[c];
                  a=c;
              }
          }

          judge[a]=true;

          for (int d =0;d<numVertices;d++){
              if (!judge[d]&&min+Weight[a][d]<dis[d]){
                  pre[d]=a;
                  dis[d]=min+Weight[a][d];
              }
          }

      }


        return dis[end];
        }



    @Override
    public void addVertex(Object vertex) {
        if ((numVertices + 1) == adjMatrix.length)
            expandCapacity();

        vertices[numVertices] = (T) vertex;
        for (int i = 0; i < numVertices; i++)
        {
            adjMatrix[numVertices][i] = false;
            adjMatrix[i][numVertices] = false;
        }
        numVertices++;
        modCount++;
    }

    @Override
    public void removeVertex(Object vertex) {
//        for (int i =0;i<vertices.length;i++){
////            if (vertices[i]==vertex){
////                removeVertex(i);
////            }
////        }
        removeVertex(getIndex((T) vertex));
        numVertices--;
    }
    public void removeVertex(int index)
    {
        for (int i = index; i < vertices.length - 1; i++) {

            vertices[i] = vertices[i + 1];
        }
        for (int i = index; i < numVertices - 1; i++) {
            for (int x = 0; x < numVertices; x++) {
                adjMatrix[i][x] = adjMatrix[i + 1][x];

            }
        }

        for (int a = index; a < numVertices; a++) {
            for (int x = 0; x < numVertices; x++) {
                adjMatrix[x][a] = adjMatrix[x][a + 1];
            }
        }


        for (int t = 0; t < numVertices; t++) {
            adjMatrix[index][t] = false;
            adjMatrix[t][index] = false;
        }
        modCount++;
        numVertices--;

    }

    @Override
    public void addEdge(Object vertex1, Object vertex2) {
        addEdge(getIndex((T) vertex1), getIndex((T) vertex2));
    }

    @Override
    public void removeEdge(Object vertex1, Object vertex2) {
        removeEdge((getIndex((T) vertex1)),getIndex((T) vertex2));
    }


    public Iterator<T> iteratorDFS(int startIndex)
    {
        Integer x;
        boolean found;
        LindedStack<Integer> traversalStack = new LindedStack<Integer>();
        UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
        boolean[] visited = new boolean[numVertices];

        if (!indexIsValid(startIndex))
            return resultList.iterator();

        for (int i = 0; i < numVertices; i++)
            visited[i] = false;

        traversalStack.push(new Integer(startIndex));
        resultList.addToRear(vertices[startIndex]);
        visited[startIndex] = true;

        while (!traversalStack.isEmpty())
        {
            x = traversalStack.peek();
            found = false;

            //Find a vertex adjacent to x that has not been visited
            //     and push it on the stack
            for (int i = 0; (i < numVertices) && !found; i++)
            {
                if (adjMatrix[x.intValue()][i] && !visited[i])
                {
                    traversalStack.push(new Integer(i));
                    resultList.addToRear(vertices[i]);
                    visited[i] = true;
                    found = true;
                }
            }
            if (!found && !traversalStack.isEmpty())
                traversalStack.pop();
        }
        return new Network.GraphIterator(resultList.iterator());
    }


    @Override
    public Iterator iteratorBFS(Object startVertex) {
        return iteratorBFS(getIndex((T) startVertex));
    }


    public Iterator<T> iteratorBFS(int startIndex)
    {
        Integer x;
        LInedQueue<Integer> traversalQueue =  new LInedQueue<Integer>();
        UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();

        if (!indexIsValid(startIndex))
            return resultList.iterator();

        boolean[] visited = new boolean[numVertices];
        for (int i = 0; i < numVertices; i++)
            visited[i] = false;

        traversalQueue.enqueue(new Integer(startIndex));
        visited[startIndex] = true;

        while (!traversalQueue.isEmpty())
        {
            x = traversalQueue.dequeue();
            resultList.addToRear(vertices[x.intValue()]);

            //Find all vertices adjacent to x that have not been visited
            //     and queue them up

            for (int i = 0; i < numVertices; i++)
            {
                if (adjMatrix[x.intValue()][i] && !visited[i])
                {
                    traversalQueue.enqueue(new Integer(i));
                    visited[i] = true;
                }
            }
        }
        return new Network.GraphIterator(resultList.iterator());
    }


    @Override
    public Iterator iteratorDFS(Object startVertex) {
        return iteratorDFS(getIndex((T) startVertex));
    }
    protected Iterator<Integer> iteratorShortestPathIndices
            (int startIndex, int targetIndex)
    {
        int index = startIndex;
        int[] pathLength = new int[numVertices];
        int[] predecessor = new int[numVertices];
       LInedQueue<Integer> traversalQueue =  new LInedQueue<>();
        UnorderedListADT<Integer> resultList =
                new ArrayUnorderedList<Integer>();

        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex) ||
                (startIndex == targetIndex))
            return resultList.iterator();

        boolean[] visited = new boolean[numVertices];
        for (int i = 0; i < numVertices; i++)
            visited[i] = false;

        traversalQueue.enqueue(new Integer(startIndex));
        visited[startIndex] = true;
        pathLength[startIndex] = 0;
        predecessor[startIndex] = -1;

        while (!traversalQueue.isEmpty() && (index != targetIndex))
        {
            index = (traversalQueue.dequeue()).intValue();

            //Update the pathLength for each unvisited vertex adjacent
            //     to the vertex at the current index.
            for (int i = 0; i < numVertices; i++)
            {
                if (adjMatrix[index][i] && !visited[i])
                {
                    pathLength[i] = pathLength[index] + 1;
                    predecessor[i] = index;
                    traversalQueue.enqueue(new Integer(i));
                    visited[i] = true;
                }
            }
        }
        if (index != targetIndex)  // no path must have been found
            return resultList.iterator();

        StackADT<Integer> stack = new LindedStack<>();
        index = targetIndex;
        stack.push(new Integer(index));
        do
        {
            index = predecessor[index];
            stack.push(new Integer(index));
        } while (index != startIndex);

        while (!stack.isEmpty())
            resultList.addToRear(((Integer)stack.pop()));

        return new Network.GraphIndexIterator(resultList.iterator());
    }


    public Iterator<T> iteratorShortestPath(int startIndex,
                                            int targetIndex)
    {
        UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
            return resultList.iterator();

        Iterator<Integer> it = iteratorShortestPathIndices(startIndex, targetIndex);
        while (it.hasNext())
            resultList.addToRear(vertices[((Integer)it.next()).intValue()]);
        return new Network.GraphIterator(resultList.iterator());
    }



    @Override
    public Iterator iteratorShortestPath(Object startVertex, Object targetVertex) {
        return iteratorShortestPath(getIndex((T) startVertex),
                getIndex((T) targetVertex));
    }


    public int shortestPathLength(int startIndex, int targetIndex)
    {
        int result = 0;
        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
            return 0;

        int index1, index2;
        Iterator<Integer> it = iteratorShortestPathIndices(startIndex, targetIndex);

        if (it.hasNext())
            index1 = ((Integer)it.next()).intValue();
        else
            return 0;

        while (it.hasNext())
        {
            result++;
            it.next();
        }

        return result;
    }

    public int shortestPathLength(T startVertex, T targetVertex)
    {
        return shortestPathLength(getIndex(startVertex), getIndex(targetVertex));
    }



    protected void expandCapacity()
    {
        T[] largerVertices = (T[])(new Object[vertices.length*2]);
        boolean[][] largerAdjMatrix =
                new boolean[vertices.length*2][vertices.length*2];

        for (int i = 0; i < numVertices; i++)
        {
            for (int j = 0; j < numVertices; j++)
            {
                largerAdjMatrix[i][j] = adjMatrix[i][j];
            }
            largerVertices[i] = vertices[i];
        }

        vertices = largerVertices;
        adjMatrix = largerAdjMatrix;
    }
    @Override
    public boolean isEmpty() {
        if (vertices[0].equals(null)){
            return true;

        }
        else {
            return false;
        }
    }
    public Object[] getVertices()
    {

        return vertices;
    }


    protected boolean indexIsValid(int index)
    {
        // To be completed as a Programming Project
        boolean a =true;
        if (vertices[index]==null){
            a=false;
        }
        return a;
    }
    public int getIndex(T vertex)
    {
        // To be completed as a Programming Project
        int a =-1;
        for (int i =0;i<vertices.length;i++){
            if (vertices[i].equals(vertex)){
                a=i;
                break;
            }

        }

        return a;
    }
    @Override
    public boolean isConnected() {
     //   boolean a =true;
//        for (int i =0;i<adjMatrix.length;i++){
//            for (int j =0;j<adjMatrix.length;j++){
//                if (adjMatrix[i][j]==false) {
//                    a=false;
//                }
//
//            }
//        }
        boolean temp =true;
        LInedQueue w = new LInedQueue();
        for(int m = 0;m<numVertices-1;m++) {
            Iterator q = iteratorBFS(m);
            while (q.hasNext()) {
                w.enqueue(q.next());
            }
            if (w.size() == numVertices) {
                temp=true;
            } else {
               temp=false;
            }
        }
        return temp;
    }

    @Override
    public int size() {
        return numVertices;
    }
    public class GraphIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;

        /**
         * Sets up this iterator using the specified iterator.
         *
         * @param iter the list iterator created by a graph traversal
         */
        public GraphIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        /**
         * The remove operation is not supported.
         *
         * @throws UnsupportedOperationException if the remove operation is called
         */
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * Inner class to represent an iterator over the indexes of this graph
     */
    protected class GraphIndexIterator implements Iterator<Integer>
    {
        private int expectedModCount;
        private Iterator<Integer> iter;

        /**
         * Sets up this iterator using the specified iterator.
         *
         * @param iter the list iterator created by a graph traversal
         */
        public GraphIndexIterator(Iterator<Integer> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        public Integer next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        /**
         * The remove operation is not supported.
         *
         * @throws UnsupportedOperationException if the remove operation is called
         */
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }

}